package com.fpf.sort.binarySearch;

import java.util.Arrays;

public class BinarySearch {

    /**
     * 二分查找基础版
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到则返回索引，找不到返回-1
     */
    public static int binarySearchBasic(int[] a, int target) {
        //设置指针的初始值
        int i = 0;
        int j = a.length - 1;
        while (i <= j) { //范围内有东西
            int m = (i + j) >>> 1;
            if (target < a[m]) { //目标在左边
                j = m - 1;
            } else if (a[m] < target) { //目标在右边
                i = m + 1;
            } else { //找到了
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找改动版
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到则返回索引，找不到返回-1
     */
    public static int binarySearchAfterNative(int[] a, int target) {
        int i = 0;
        int j = a.length;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找平衡版
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到则返回索引，找不到返回-1
     */
    public static int binarySearchBalance(int[] a, int target) {
        int i = 0;
        int j = a.length;
        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (a[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

    /**
     * 二分查找Java版
     * <p>
     * 找到则返回索引，找不到返回（-（插入点）-1）
     */
    public static void main(String[] args) {
        int[] a = {2, 5, 7, 9};
        int target = 11;
        int i = Arrays.binarySearch(a, target);
        System.out.println(i);
        if (i < 0) {
            int insertIndex = Math.abs(i + 1);// 插入点索引
            int[] b = new int[a.length + 1];
            System.arraycopy(a, 0, b, 0, insertIndex);
            b[insertIndex] = target;
            System.arraycopy(a, insertIndex, b, insertIndex + 1, a.length - insertIndex);
            System.out.println(Arrays.toString(b));
        }
    }

    /**
     * 二分查找 Leftmost
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到则返回索引，找不到返回-1
     */
    public static int binarySearchLeftmost1(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else { //记录候选位置
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找 Rightmost
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到则返回索引，找不到返回-1
     */
    public static int binarySearchRightmost1(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else { //记录候选位置
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找 Leftmost
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 返回 >=target的最靠左的索引
     */
    public static int binarySearchLeftmost2(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    /**
     * 二分查找 Rightmost
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 返回 <=target的最靠右的索引
     */
    public static int binarySearchRightmost2(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i + 1;
    }
}
